import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().permute(new int[]{1, 2, 3}));
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>(nums.length);
        for (int each : nums) {
            cur.add(each);
        }
        backtracking(cur, 0, ans);
        return ans;
    }

    void backtracking(List<Integer> cur, int i, List<List<Integer>> ans) {
        if (i == cur.size()) {
            ans.add(new ArrayList<>(cur));
        }
        for (int j = i; j < cur.size(); j++) {
            Collections.swap(cur, i, j);    //把元素j交换到前面
            backtracking(cur, i + 1, ans);
            Collections.swap(cur, i, j);    //再交换回去
        }
    }
}
